/**
 * //给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。
 * //
 * // 示例 1：
 * //
 * // 输入: num = 1775(110111011112)
 * //输出: 8
 * //
 * //
 * // 示例 2：
 * //
 * // 输入: num = 7(01112)
 * //输出: 4
 * //
 * //
 * // Related Topics 位运算 动态规划 👍 87 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID_interview_05_03_ReverseBitsLcci {
    public static void main(String[] args) {
        Solution solution = new ID_interview_05_03_ReverseBitsLcci().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int reverseBits(int num) {

            if (num == 0) return 1;

            //翻转一次连续1的长度
            int res = 0;
            //当前连续1的个数
            int cur = 0;
            //0之前的连续1个数
            int lastOneCount = 0;

            while (num != 0) {

                if ((num & 1) == 1) { //如果第i位 == 1, 连续1个数++
                    cur++;
                } else { //如果第i位是 == 0;
                    //连续1中断，赋值到0之前连续1上
                    //如果连续两个0， lastOneCount就等于0
                    lastOneCount = cur;
                    //连续1归0
                    cur = 0;
                }

                res = Math.max(res, cur + lastOneCount + 1); //最长等于 前半段+后半段+ 翻转一次
                //逻辑右移，开头补0
                num = num >>> 1;

            }


            return res == 33 ? 32 : res;


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}